\chapter{Fundamentação Teórica}

\section{Floresta de Caminhos Ótimos - OPF}

O problema de reconhecimento de padrões pode ser modelado para o uso de floresta de caminhos ótimos em um grafo, definido em seu espaço de atributos. Os nós são as amostras, sendo representadas pelos seus respectivos vetores de atributos, e os arcos definidos por uma relação de adjacência entre as amostras \cite{rit01}\cite{rit02}. Tanto os nós quanto os arcos, podem ser ponderados, tendo a possibilidade de aplicação de diversas funções de custo. Com isso, é possível o particionamento do grafo em árvores de caminhos ótimos, sendo enraizadas pelos seus respectivos protótipos (sementes) na fase de treinamento, e a classificação de uma amostra qualquer sendo o mesmo rótulo do protótipo mais fortemente conexo. A seguir apresentaremos a técnica OPF, seguindo a heurística de análise dos dados sobre um grafo completo e seleção dos protótipos como sendo as amostras mais próximas de classes distintas.

\subsection{Definição}

O cálculo de caminhos ótimos para as demais amostras são computadas pelo algoritmo de Transformada Imagem Floresta (IFT)\cite{FalcaoTPAMI04}. A técnica IFT é essencialmente o algoritmo de Dijkstra, modificado para receber várias fontes e aplicação de outras funções de custo. Seu comportamento inicialmente identifica os mínimos da função de custo como os nós de origem e se propaga em ordem não decrescente a fim de melhores caminhos, particionando o grafo em uma floresta de caminhos ótimos onde as raízes são os protótipos selecionados.
Atualmente Papa\cite{papaOPF}, apresentou um novo modelo de classificador supervisionados baseado em OPF. A técnica usa como modelo de relação de adjacência um grafo de conexão completa, uma função de custo $f_{max}$, dada pela Equação \ref{eqFMAX}, e escolhe os protótipos a partir da árvore resultante gerada pela técnica Minimum Spanning Tree (MST). 

\begin{equation}
f_{max}(\pi_s . \langle s \rangle) = max\{f_{max}(\pi_s),d(s,t)\},
\label{eqFMAX}
\end{equation}

\subsection{Classificador OPF baseado em grafo completo}

Dado ($Z_1$,$A_1$), ($Z_2,A_1$) and ($Z_3$,$A_1$) grafos completos, representando as amostras de treinamento, avaliação e classificação respectivamente, como apresentado na Figura \ref{pixelCentral}(a). Seja $\lambda(s)$ um função que atribui o rótulo correto $i$ $\{1,2,...,c\}$ da classe $i$ para qualquer amostra $s$ $\in$ $Z_1$ $\cup$ $Z_2$ $\cup$ $Z_3$, $S$ um conjunto de protótipos de todas as classes, sendo $S$ $\subset$ $Z_1$, e $v$ um algoritmo que extrai $n$ atributos como: textura, cor, formas geométricas) de qualquer amostra $s$ $\in$ $Z_1$ $\cup$ $Z_2$ $\cup$ $Z_3$ retornando um vetor $\vec{v}(s)$. A distância $d(s,t)\geq 0$, entre duas amostras, $s$ e $t$, é somente um valor entre os vetores de características $\vec{v}(s)$ e $\vec{v}(t)$. Pode-se usar qualquer função distância, mas para a abordagem de Papa\cite{papaOPF} sobre grafo completo, se utiliza distância Euclediana $\mid \mid \vec{v}(t)$ - $\vec{v}(s) \mid \mid$.

\begin{figure}[!htbp]
\begin{center}
$ \begin{array}{ccc}
\includegraphics[scale=0.30]{2a.jpg} &
\includegraphics[scale=0.30]{2b.jpg} &
\includegraphics[scale=0.30]{2c.jpg} \\
(a) & (b) & (c)
\end{array} $
$ \begin{array}{ccc}
\includegraphics[scale=0.30]{2d.jpg} &
\includegraphics[scale=0.30]{2e.jpg} &
\includegraphics[scale=0.30]{2f.jpg} \\
(d) & (e) & (f)
\end{array} $

\caption{(a) Grafo completo ponderado nas arestas. (b) Grafo MST referente ao grafo completo. (c) Protótipos selecionados a partir da heurística de elementos adjacentes de classes distintas na MST. (d) Amostra de teste e suas conexões em todos os elementos do grafo de treinamento. (e) Caminho ótimo do protótipo mais fortemente conexo. (f) Permanência da amostra anterior classificada, e inclusão de uma nova amostra para classificação.}
\label{pixelCentral}
\end{center} 
\end{figure}

O problema de classificação nada mais é do que rotular a classe correta $\lambda(s)$, para qualquer amostra $s$ $\in$ $Z_3$. A fase de treinamento consiste em encontrar um subgrupo de protótipos $S^{*}$ $\subset$ $Z_1$, e a classificação de qualquer amostra $s$ $\in$ $Z_3$, é feita através da avaliação de forma incremental atribuindo a ele o 
rótulo do protótipo mais fortemente conexo. 

\subsection{Fase de Treinamento}

Dado um grafo completo $(Z_1,A)$ o treinamento consiste em encontrar protótipos para $S^{*}$, através da Árvore Geradora Mínina (MST) e Floresta de Caminhos Ótimos com raízes em $S^{*}$. Assumindo que conhecemos o conjunto $S*$, o Algoritmo 1 de Floresta de Caminhos Ótimos (FCO), propaga os rótulos dos protótipos para todas as amostras de suas respectivas árvores de caminhos ótimos, formando um mapa de rótulos $L(s)$ $\in$ $\{1,2,...,c\}$.
\incmargin{1em}
\linesnumbered
\begin{algorithm}
\caption{Algoritmo FCO}
\Entrada{Conjunto Z, protótipos $S*$ $\subset$ $Z$ e o par $(v,d)$ para extração de características e cálculos de distâncias.}
\Saida{Floresta de caminhos ótimos P, mapa de valores ótimos V, e mapa de rótulos L.}
\Dados{Fila Q de prioridades e variável tmp}
\BlankLine
\ParaCada{s $\in$ $Z/ \ S*$}
{
$V(s)\longleftarrow +\infty,$
}
\ParaCada{s $\in$ $ S*$}
{
$V(s)\longleftarrow 0,$
$P(s)\longleftarrow nil,$
$L(s)\longleftarrow \lambda(s),$
e insira s em Q.
}
\Enqto{Q não estiver vazia}
{
Remova de Q uma amostra $s$ tal que V(s) seja mínimo. \\
\ParaCada{t $\in$ Z tal que $t \neq s$ e $V(t)>V(s)$}
{
Calcule tmp $\longleftarrow$ $max\{V(s), d(s,t)\}$.\\
\Se{$tmp < V(t)$}
{
\Se{V(t) $\neq$ $+\infty$}
{
Remova t de Q.
}
$P(t)\longleftarrow s, L(t)\longleftarrow L(s), V(t)\longleftarrow tmp.$ Insira t em Q.
}
}
}
\Retorna{P,R,V}
\label{algorithmOPF}
\end{algorithm}
\decmargin{1em}

O processo de treinamento do classificador supervisionado baseado em Floresta de Caminhos Ótimos, usando grafo completo Figura \ref{pixelCentral}(a), consiste em encontrar um conjunto de protótipos $S^{*}$, de modo que os elementos sejam considerados os mais representativos. Várias heurísticas podem ser adotadas, entretanto o modo de seleção pode afetar o desempenho do classificador. Um processo de seleção sugerido por \cite{papaOPF}, para seleção de protótipos sobre grafos completos, é o uso do grafo gerado sobre um $MST$ (Árvore Geradora Mínima). Computando uma $MST$ no grafo completo $(Z,A)$ Figura \ref{pixelCentral}(b), obtemos um grafo conexo acíclico, cujos nós são todas as amostras em $Z_1$, e os arcos são não direcionados e ponderados. A soma dos pesos de seus arcos é mínima, se comparada a outras árvores geradoras no grafo completo, com isso obtemos uma árvore geradora ótima. Dessa forma, os protótipos a serem selecionados, são os elementos mais próximos de classes diferentes Figura \ref{pixelCentral}(c). Removendo-se os arcos entre as classes diferentes, essas amostras adjacentes serão os protótipos em $S^{*}$. Um ponto importante, é que uma classe pode conter vários protótipos (árvore de caminhos ótimos), mas devemos sempre garantir que toda classe, deva ter no mínimo um protótipo. O Algoritmo 2, apresenta uma modificação sobre o Algoritmo 1, para calcular uma árvore de peso mínimo $MST$, e selecionar os protótipos para $S*$, apresentando semelhanças ao algoritmos de $Prim$.

\incmargin{1em}
\linesnumbered
\begin{algorithm}
\caption{Algoritmo MST}
\Entrada{Conjunto Z, par $(v,d)$ para extração de características e cálculos de distâncias}
\Saida{Árvore de peso mínimo P, mapa de valores V e protótipos $S*$}
\Dados{Fila Q de prioridades, status() e variável tmp}
\BlankLine
\ParaCada{s $\in$ Z/$t_0$}
{
$V(s)\longleftarrow +\infty,$
$status(s)\longleftarrow 0.$
}
V($t_0$)$\longleftarrow$ 0, P($t_0$)$\longleftarrow$ nil, status($t_0$)$\longleftarrow$ 1, e insira $t_0$, em Q.\\
\Enqto{Q não estiver vazia}
{
Remova de Q uma amostra s tal que V(s), é mínimo e faça status(s)$\longleftarrow$ 2.\\
\Se{P(s) $\neq$ nil}
{
\Se{$\lambda(s)$ $\neq$ $\lambda(P(s))$}
{
$S*$ $\longleftarrow$ $S*$ $\cup$ $\{s,P(s)\}$
}
}
\ParaCada{t $\in$ Z tal que $t\neq s$ e $status(t)\neq 2$}
{
Calcule tmp $\longleftarrow$ d(s,t). \\
\Se{$tmp < V(t)$}
{
\Se{status(t) = 1}
{
Remova t de Q.
}
P(t) $\longleftarrow$ s e V(t) $\longleftarrow$ tmp.
\\
Insira t em Q e faça $status(t)\longleftarrow 1$.
}
}
}
\label{algorithmMST}
\end{algorithm}
\decmargin{1em}

\subsection{Fase de Classificação}

A classificação de uma nova amostra $t$, considera todas as conexões entre $t$ e as amostras $s$ de treinamento, como se $t$ fizesse parte do grafo original. A partir de todos os possíveis caminhos entre o conjunto $S$ até $t$, o objetivo na classificação está em encontrar o caminho ótimo $P*(t)$, de $S$ até $t$, com a classe $\lambda(R(t))$ de seu protótipo R(t) $\in$ S, mais fortemente conexo. O caminho pode ser encontrado incrementalmente, avaliando o valor de custo ótimo $V(t)$, pela Equação \ref{eqClassificacao} aplicado $\forall s$ $\in$ Z.

\begin{equation}
V(t) = min\{max\{V(s),d(s,t)\}\}.
\label{eqClassificacao}
\end{equation}

Seja $s*$ $\in$ Z, que satisfaz a Equação \ref{eqClassificacao}, (predecessor P(t) = $s*$). Dado que $L(s*)$ = $\lambda(R(t))$, classificação é realizada associando o rótulo de $L(s*)$ com sendo a classe de $t$. O erro de classificação ocorre quando $L(s*)$ $\neq$ $\lambda(t)$.
